package cn.handong.tool.algorithm.迷宫;

import java.util.LinkedList;
import java.util.Queue;
 
public class MazeSearch2 {
    private static final String[] mazeString = {
            "01010101001011001001010110010110100100001000101010",
            "00001000100000101010010000100000001001100110100101",
            "01111011010010001000001101001011100011000000010000",
            "01000000001010100011010000101000001010101011001011",
            "00011111000000101000010010100010100000101100000000",
            "11001000110101000010101100011010011010101011110111",
            "00011011010101001001001010000001000101001110000000",
            "10100000101000100110101010111110011000010000111010",
            "00111000001010100001100010000001000101001100001001",
            "11000110100001110010001001010101010101010001101000",
            "00010000100100000101001010101110100010101010000101",
            "11100100101001001000010000010101010100100100010100",
            "00000010000000101011001111010001100000101010100011",
            "10101010011100001000011000010110011110110100001000",
            "10101010100001101010100101000010100000111011101001",
            "10000000101100010000101100101101001011100000000100",
            "10101001000000010100100001000100000100011110101001",
            "00101001010101101001010100011010101101110000110101",
            "11001010000100001100000010100101000001000111000010",
            "00001000110000110101101000000100101001001000011101",
            "10100101000101000000001110110010110101101010100001",
            "00101000010000110101010000100010001001000100010101",
            "10100001000110010001000010101001010101011111010010",
            "00000100101000000110010100101001000001000000000010",
            "11010000001001110111001001000011101001011011101000",
            "00000110100010001000100000001000011101000000110011",
            "10101000101000100010001111100010101001010000001000",
            "10000010100101001010110000000100101010001011101000",
            "00111100001000010000000110111000000001000000001011",
            "10000001100111010111010001000110111010101101111000"};
 
    /**
     * 根据 字符串数组迷宫 转换为 整型数组迷宫
     */
    private static final char[][] maze = new char[30][50];
 
    /**
     * 方位，字典序 D < L < R < U
     */
    private static final char[] direction = {'D', 'L', 'R', 'U'};
 
    /**
     * 方位，用于计算
     */
    private static final int[][] step = { // 右下↘为1 , 左上↖为-1
            {1, 0},     // D 下 1
            {0, -1},    // L 左 -1
            {0, 1},     // R 右 1
            {-1, 0}};   // U 上 -1
 
    /**
     * 记录每个位置 是否被访问过
     * <p>用 1 表示访问过，0 表示没有访问过</p>
     */
    private static final int[][] visitFlag = new int[30][50];
 
    /**
     * 记录每个位置 是从上一个坐标的哪个方位得来的
     * <p>用 i 记录，其中 direction[i]依次代表 D、L、R、U</p>
     */
    private static final int[][] directionRemember = new int[30][50];
 
    /**
     * 队列保存 广度优先搜索 经过的每一个点位置信息
     * <p>点坐标表示方法：当前位置所在行 * 每行的个数 + 当前位置所在列
     */
    private static final Queue<Integer> location = new LinkedList<>();
 
    /**
     * 广度优先遍历
     * <p>寻找所有从终点到起点的路线，求每一个位置到终点的距离，并存放在direction中</p>
     */
    public static void bfs() {
        int nowX, nowY;
        while (!location.isEmpty()) {
            int now = location.poll();
            nowX = now / 50;
            nowY = now % 50;
 
            for (int i = 0; i < 4; i++) {
                int nextX = nowX + step[i][0]; // step[i][0] 按照 D L R U 的次序
                int nextY = nowY + step[i][1]; // step[i][1] 按照 D L R U 的次序
 
                // nextX >= 0 && nextX < 30 位置合法
                // nextY >= 0 && nextY < 50 位置合法
                // maze[nextX][nextY] == '0' 不是墙壁
                // visitFlag[nextX][nextY] == 0 没有被访问过
                if ((nextX >= 0 && nextX < 30) && (nextY >= 0 && nextY < 50) &&
                        maze[nextX][nextY] == '0' && visitFlag[nextX][nextY] == 0) {
 
                    // visitFlag记录访问过
                    visitFlag[nextX][nextY] = 1;
                    // directionRemember 记住该坐标是从上一个坐标的哪个方位得来的
                    directionRemember[nextX][nextY] = i;
                    // 队列保存本次判断的位置，用于后面的广度优先搜索
                    location.add(nextX * 50 + nextY);
                    // 若到入口,则退出
                    if (nextX == 0 && nextY == 0) break;
                }
            }
        }
    }
 
    /**
     * 深度优先搜索
     * <p>寻找所有从终点到起点的路线，根据directionRemember的方位记录（R、L、D、U），依次找到路径</p>
     * @param start 从终点开始搜索
     * @return 到当前点的 route 串
     */
    public static String dfs(int start) {
        int nowX = start / 50;
        int nowY = start % 50;
        String route = "";
        if (nowX != 0 || nowY != 0) {
            // i 为该坐标是从上一个坐标的哪个方位来的
            int i = directionRemember[nowX][nowY];
            // 相减，得到上一个坐标点
            int nextX = nowX - step[i][0];
            int nextY = nowY - step[i][1];
            // 记录当前点的 route 串
            route = dfs(nextX * 50 + nextY) + direction[i];
        }
        return route;
    }
 
    public static void main(String[] args) {
        // 读入迷宫
        for (int i = 0; i < 30; i++)
            maze[i] = mazeString[i].toCharArray();
 
        // 从入口往出口广度优先搜索，添加起点坐标，0 * 50 + 0表示位置
        location.add(0 * 50 + 0);
        bfs();
        String route = dfs(29 * 50 + 49);
        System.out.println(route);
    }
}